{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Reverse Words in a String II"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #two-pointers #string"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #双指针 #字符串"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: reverseWords"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #反转字符串中的单词 II"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个字符数组 <code>s</code> ，反转其中 <strong>单词</strong> 的顺序。</p>\n",
    "\n",
    "<p><strong>单词</strong> 的定义为：单词是一个由非空格字符组成的序列。<code>s</code> 中的单词将会由单个空格分隔。</p>\n",
    "\n",
    "<div class=\"original__bRMd\">\n",
    "<div>\n",
    "<p>必须设计并实现 <strong>原地</strong> 解法来解决此问题，即不分配额外的空间。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>s = [\"t\",\"h\",\"e\",\" \",\"s\",\"k\",\"y\",\" \",\"i\",\"s\",\" \",\"b\",\"l\",\"u\",\"e\"]\n",
    "<strong>输出：</strong>[\"b\",\"l\",\"u\",\"e\",\" \",\"i\",\"s\",\" \",\"s\",\"k\",\"y\",\" \",\"t\",\"h\",\"e\"]\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>s = [\"a\"]\n",
    "<strong>输出：</strong>[\"a\"]\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= s.length &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>s[i]</code> 可以是一个英文字母（大写或小写）、数字、或是空格 <code>' '</code> 。</li>\n",
    "\t<li><code>s</code> 中至少存在一个单词</li>\n",
    "\t<li><code>s</code> 不含前导或尾随空格</li>\n",
    "\t<li>题目数据保证：<code>s</code> 中的每个单词都由单个空格分隔</li>\n",
    "</ul>\n",
    "</div>\n",
    "</div>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [reverse-words-in-a-string-ii](https://leetcode.cn/problems/reverse-words-in-a-string-ii/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [reverse-words-in-a-string-ii](https://leetcode.cn/problems/reverse-words-in-a-string-ii/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[\"t\",\"h\",\"e\",\" \",\"s\",\"k\",\"y\",\" \",\"i\",\"s\",\" \",\"b\",\"l\",\"u\",\"e\"]', '[\"a\"]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseWords(self, s: List[str]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify s in-place instead.\n",
    "        \"\"\"\n",
    "        def helper(l, r):\n",
    "            while l < r:\n",
    "                s[l], s[r] = s[r], s[l]\n",
    "                l += 1\n",
    "                r -= 1\n",
    "        helper(0, len(s)-1)\n",
    "        l = 0\n",
    "        for i, ch in enumerate(s):\n",
    "            if ch == ' ':\n",
    "                helper(l, i-1)\n",
    "                l = i+1\n",
    "        helper(l, len(s)-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseWords(self, s: List[str]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify s in-place instead.\n",
    "        \"\"\"\n",
    "        if not s:\n",
    "            return s\n",
    "        def re(s, i, j):\n",
    "\n",
    "            while i<j:\n",
    "                s[i],s[j] = s[j],s[i]\n",
    "                i+=1\n",
    "                j-=1\n",
    "        \n",
    "        re(s, 0, len(s)-1)\n",
    "        print(s)\n",
    "        pre = 0\n",
    "        for j,v in enumerate(s):\n",
    "            if v == ' ':\n",
    "                re(s, pre, j-1)\n",
    "                pre = j+1\n",
    "        print(j, pre)\n",
    "        re(s, pre, j)\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseWords(self, s: List[str]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify s in-place instead.\n",
    "        \"\"\"\n",
    "\n",
    "        start = 0\n",
    "        end = len(s)-1\n",
    "        #翻转整个数组     \n",
    "        while start < end:\n",
    "            s[start], s[end]  =  s[end],s[start]\n",
    "            start +=1\n",
    "            end -= 1\n",
    "\n",
    "        #翻转每个单词\n",
    "        start = 0\n",
    "        end = 0\n",
    "        \n",
    "        while start < len(s):         \n",
    "            if s[start] == \" \"  or start == len(s)-1:\n",
    "                if start == len(s)-1:\n",
    "                    word_e = start\n",
    "                else:\n",
    "                    word_e = start-1\n",
    "                word_f = end \n",
    "                while word_f<word_e:\n",
    "                    s[word_f],s[word_e] = s[word_e],s[word_f]\n",
    "                    word_e -= 1\n",
    "                    word_f += 1\n",
    "                if start!= len(s)-1:\n",
    "                    end = start + 1\n",
    "            start += 1\n",
    "\n",
    "        return s"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseWords(self, s):\n",
    "        \"\"\"\n",
    "        Do not return anything, modify s in-place instead.\n",
    "        \"\"\"\n",
    "        def reverse(array, start, end):\n",
    "            p, q = start, end\n",
    "            while p < q:\n",
    "                array[p], array[q] = array[q], array[p]\n",
    "                p += 1\n",
    "                q -= 1\n",
    "            pass\n",
    "        reverse(s, 0, len(s) - 1)\n",
    "        p = 0\n",
    "        for i in range(len(s)):\n",
    "            if s[i] == ' ':\n",
    "                reverse(s, p, i - 1)\n",
    "                p = i + 1\n",
    "        reverse(s, p, len(s) - 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseWords(self, s: List[str]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify s in-place instead.\n",
    "        \"\"\"\n",
    "        s[:] = ' '.join(''.join(s).split()[::-1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseWords(self, s: List[str]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify s in-place instead.\n",
    "        \"\"\"\n",
    "        words = []\n",
    "        stack = []\n",
    "        for i in range(0 , len(s)):\n",
    "            if s[i] != \" \":\n",
    "                words.append(s[i])\n",
    "            if s[i] == \" \":\n",
    "                stack.append(words)\n",
    "                words = []\n",
    "            if i == len(s) - 1:\n",
    "                stack.append(words)\n",
    "        #print(stack)\n",
    "        s2 = []\n",
    "        for i in range(0, len(stack)):\n",
    "            s2.append(stack.pop())\n",
    "        #print(len(s2))\n",
    "        k = 0\n",
    "        s3 = [' '] * len(s)\n",
    "        #print(s3)\n",
    "        #print(len(s))\n",
    "        #s = [' '] * len(s)\n",
    "        for i in range(0, len(s2)):\n",
    "            #print(len(s2[i]))\n",
    "            s3[k:len(s2[i])] = s2[i]\n",
    "            #print(s)\n",
    "            if i != len(s2) - 1:\n",
    "                s3[k+len(s2[i])] = \" \"\n",
    "            k += (len(s2[i]) + 1)\n",
    "        for i in range(0, len(s)):\n",
    "            s[i] = s3[i]\n",
    "        #print(s3)\n",
    "        #s = s3\n",
    "        #print(len(s))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseWords(self, s: List[str]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify s in-place instead.\n",
    "        \"\"\"\n",
    "        space_index = [-1]\n",
    "        for i in range(len(s)):\n",
    "            if s[i] == \" \":\n",
    "                space_index.append(i)\n",
    "        \n",
    "        post = len(s)\n",
    "        ans = []\n",
    "        for t in reversed(space_index):\n",
    "            ans += s[t+1:post]+[' ']\n",
    "            post = t\n",
    "        for i in range(len(s)):\n",
    "            s[i] = ans[i]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseWords(self, s: List[str]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify s in-place instead.\n",
    "        \"\"\"\n",
    "        s.reverse()\n",
    "\n",
    "        s.append(\" \")\n",
    "\n",
    "        start = 0\n",
    "\n",
    "        for i in range(len(s)):\n",
    "            if s[i] == \" \":\n",
    "                s[start:i]= reversed(s[start:i])\n",
    "                start = i + 1\n",
    "        print(s)\n",
    "        s.pop()# pop 最后的空格"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseWords(self, s: List[str]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify s in-place instead.\n",
    "        \"\"\"\n",
    "        \n",
    "        i = 0\n",
    "        for j in range(len(s)):# aT bT c\n",
    "            if s[j] != \" \":\n",
    "                continue\n",
    "            self.reverse(s,i,j)\n",
    "            i = j + 1\n",
    "        self.reverse(s,i,len(s)) # aT bT cT\n",
    "        self.reverse(s,0,len(s)) # c b a\n",
    "# 定义翻转函数\n",
    "    def reverse(self,s,i,j):\n",
    "        left = i\n",
    "        right = j - 1\n",
    "        while left < right:\n",
    "            s[left],s[right] = s[right],s[left]\n",
    "            left += 1\n",
    "            right -= 1    \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseWords(self, s: [str]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify str in-place instead.\n",
    "        \"\"\"\n",
    "        i = 0\n",
    "        for j in range(len(s)): # aT bT c\n",
    "            if s[j] != ' ': continue\n",
    "            self.reverse(s, i, j)\n",
    "            i = j + 1\n",
    "        self.reverse(s, i, len(s)) # aT bT cT\n",
    "        self.reverse(s, 0, len(s)) # c b a\n",
    "    def reverse(self, s, i, j):\n",
    "        for k in range(i, (i + j) // 2):\n",
    "            g = j - 1 - k + i\n",
    "            s[k], s[g] = s[g], s[k]\n",
    "\n",
    "        \"\"\"\n",
    "        Do not return anything, modify s in-place instead.\n",
    "        \"\"\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseWords(self, s: List[str]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify s in-place instead.\n",
    "        \"\"\"\n",
    "        if not s:\n",
    "            return\n",
    "        self.reverse(s, 0, len(s)-1)\n",
    "        i = 0\n",
    "        for j in range(len(s)):\n",
    "            if s[j] == ' ':\n",
    "                self.reverse(s, i, j-1)\n",
    "                i = j + 1\n",
    "        self.reverse(s, i, j)\n",
    "    \n",
    "    def reverse(self, s, l, r):\n",
    "        while l < r:\n",
    "            s[l], s[r] = s[r], s[l]\n",
    "            l += 1\n",
    "            r -= 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseWords(self, s: List[str]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify s in-place instead.\n",
    "        \"\"\"\n",
    "        s[:] = s[::-1]\n",
    "        l, r = -1, 0\n",
    "        while r < len(s):\n",
    "            if s[r] == \" \":\n",
    "                s[l + 1:r] = reversed(s[l + 1:r])\n",
    "                l = r\n",
    "            r += 1\n",
    "        s[l + 1:r] = reversed(s[l + 1:r])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseWords(self, s: List[str]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify s in-place instead.\n",
    "        \"\"\"\n",
    "        s.reverse()\n",
    "        n = len(s)\n",
    "        t = ''\n",
    "        for i in range(n):\n",
    "            # print(t)\n",
    "            if s[i] != ' ':\n",
    "                t+=s[i]\n",
    "            elif s[i] == ' ':\n",
    "                s[i-len(t):i] = list(t[::-1])\n",
    "                t= ''\n",
    "        s[n-len(t):n] = list(t[::-1])\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseWords(self, s: List[str]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify s in-place instead.\n",
    "        \"\"\"\n",
    "        s.reverse()\n",
    "        n = len(s)\n",
    "        t = ''\n",
    "        for i in range(n):\n",
    "            # print(t)\n",
    "            if s[i] != ' ':\n",
    "                t+=s[i]\n",
    "            elif s[i] == ' ':\n",
    "                s[i-len(t):i] = list(t[::-1])\n",
    "                t= ''\n",
    "        s[n-len(t):n] = list(t[::-1])\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseWords(self, s: List[str]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify s in-place instead.\n",
    "        \"\"\"\n",
    "        res = ' '.join(''.join(s).split(' ')[::-1])\n",
    "        for i in range(len(s)):\n",
    "            s[i] = res[i]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseWords(self, s: List[str]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify s in-place instead.\n",
    "        \"\"\"\n",
    "        s[:]=[i for i in \" \".join(\"\".join(s).split()[::-1])]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseWords(self, s: List[str]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify s in-place instead.\n",
    "        \"\"\"\n",
    "\n",
    "        word = \"\"\n",
    "        result = \"\"\n",
    "        for c in s:\n",
    "            if c != \" \":\n",
    "                word += c\n",
    "            else:\n",
    "                result = word + \" \" + result\n",
    "                word = \"\"\n",
    "        \n",
    "        result = word + \" \" + result\n",
    "\n",
    "        for i in range(len(s)):\n",
    "            s[i] = result[i]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseWords(self, s: List[str]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify s in-place instead.\n",
    "        \"\"\"\n",
    "\n",
    "        word = \"\"\n",
    "        result = \"\"\n",
    "        for c in s:\n",
    "            if c != \" \":\n",
    "                word += c\n",
    "            else:\n",
    "                result = word + \" \" + result\n",
    "                word = \"\"\n",
    "        \n",
    "        result = word + \" \" + result\n",
    "\n",
    "        for i in range(len(s)):\n",
    "            s[i] = result[i]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseWords(self, s: List[str]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify s in-place instead.\n",
    "        \"\"\"\n",
    "        s[:] = [str for str in ' '. join(''.join(s).split()[::-1])]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseWords(self, s: List[str]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify s in-place instead.\n",
    "        \"\"\"\n",
    "        n = len(s)\n",
    "\n",
    "        tmp = []\n",
    "        t = \"\"\n",
    "        for i in range(n):\n",
    "            if s[i] != \" \":\n",
    "                t += s[i]\n",
    "            else:\n",
    "                tmp.append(t)\n",
    "                t = \"\" \n",
    "        tmp.append(t)\n",
    "        \n",
    "        k = 0\n",
    "        for i in range(len(tmp)-1, -1, -1):\n",
    "            for j in range(len(tmp[i])):\n",
    "                s[k] = tmp[i][j]\n",
    "                k += 1\n",
    "            \n",
    "            if i>0:\n",
    "                s[k] = \" \"\n",
    "                k += 1\n",
    "            \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseWords(self, s: List[str]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify s in-place instead.\n",
    "        \"\"\"\n",
    "        l = ''.join(s).split(' ')\n",
    "        l.reverse()\n",
    "        ls = ' '.join(l)\n",
    "        for i in range(len(s)):\n",
    "            s[i] = ls[i]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseWords(self, s: List[str]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify s in-place instead.\n",
    "        \"\"\"\n",
    "        s.reverse()\n",
    "        str1= ''.join(s)\n",
    "        str_arr = str1.split(' ')\n",
    "        res = ''\n",
    "        index = 0\n",
    "        for i in str_arr:\n",
    "            length = len(i)\n",
    "            s[index:index+length]= list(i[::-1])\n",
    "            index += length + 1 \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseWords(self, s: List[str]) -> None:\n",
    "        #直接模拟即可\n",
    "        a=\"\".join(s)\n",
    "        cur=a.split(\" \")[::-1]\n",
    "        res=[]\n",
    "        for i in range(len(cur)):\n",
    "            res.extend(list(cur[i]))\n",
    "            if i<len(cur)-1:\n",
    "                res.append(\" \")\n",
    "        for i in range(len(s)):\n",
    "            s[i]=res[i]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseWords(self, s: List[str]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify s in-place instead.\n",
    "        \"\"\"\n",
    "        s[:] = list(' '.join(''.join(s).split()[::-1]))\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseWords(self, s: [str]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify str in-place instead.\n",
    "        \"\"\"\n",
    "        i = 0\n",
    "        for j in range(len(s)): # aT bT c\n",
    "            if s[j] != ' ': \n",
    "                continue\n",
    "            self.reverse(s, i, j)\n",
    "            i = j + 1\n",
    "        self.reverse(s, i, len(s)) # aT bT cT\n",
    "        self.reverse(s, 0, len(s)) # c b a\n",
    "\n",
    "    def reverse(self, s, i, j):\n",
    "        for k in range(i, (i + j) // 2):\n",
    "            g = j - 1 - k + i\n",
    "            s[k], s[g] = s[g], s[k]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseWords(self, s: List[str]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify s in-place instead.\n",
    "        \"\"\"\n",
    "        left, right = 0, len(s)-1\n",
    "        while left < right:\n",
    "            s[left], s[right] = s[right], s[left]\n",
    "            left += 1\n",
    "            right -= 1\n",
    "        last_pos = -1\n",
    "        pos = 0\n",
    "        while pos <= len(s):\n",
    "            if pos == len(s) or s[pos] == \" \":\n",
    "                left = last_pos + 1\n",
    "                right = pos - 1\n",
    "                while left < right:\n",
    "                    s[left], s[right] = s[right], s[left]\n",
    "                    left += 1\n",
    "                    right -= 1\n",
    "                last_pos = pos\n",
    "            pos += 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseWords(self, s: List[str]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify s in-place instead.\n",
    "        \"\"\"\n",
    "        self.reverse(s, 0, len(s)-1)\n",
    "\n",
    "        i, j = 0, 0\n",
    "\n",
    "        while j <= len(s):\n",
    "            if j == len(s) or  s[j] == ' ' :\n",
    "                self.reverse(s, i, j-1)\n",
    "                i = j + 1\n",
    "                j = i + 1\n",
    "            else:\n",
    "                j += 1\n",
    "\n",
    "    def reverse(self, s, i, j):\n",
    "\n",
    "        k = (j - i + 1) // 2\n",
    "\n",
    "        for t in range(k):\n",
    "            s[i+t], s[j-t] = s[j-t], s[i+t]"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
